package leetcode_周赛._2023._04;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 第 340 场周赛
 * AC_0
 * @author yezh
 * @date 2023/4/10 14:40
 */
public class _09 {

    public static void main(String[] args) {
        System.out.println(isZhiShu(883));
    }

    /**
     * 对角线上的质数
     * 算法: 数学
     * 1 既不是质数也不是素数
     */
    public int diagonalPrime(int[][] nums) {
        int ans = 0, n = nums.length;
        for (int i = 0; i < n; i++) if (ans < nums[i][i] && isZhiShu(nums[i][i])) ans = nums[i][i];
        for (int i = n - 1; i >= 0; i--)
            if (ans < nums[i][n - i - 1] && isZhiShu(nums[i][n - i - 1])) ans = nums[i][n - i - 1];
        return ans;
    }

    static boolean isZhiShu(int num) {
        for (int i = 2; i <= Math.sqrt(num); i++) if (num % i == 0) return false;
        return num >= 2;
    }

    /**
     * 等值距离和
     * 算法: 前缀和 + 二分查找
     * 跟上上周赛的第三题很像, 算一个数与其他数的距离, 相当于求将所有数变成当前数所需的次数
     */
    public long[] distance(int[] nums) {
        int n = nums.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            List<Integer> list = map.getOrDefault(nums[i], new ArrayList<>());
            list.add(i);
            map.put(nums[i], list);
        }
        long[] ans = new long[n];
        long[] prefix = new long[n + 1];
        for (List<Integer> list : map.values()) {
            int size = list.size();
            for (int i = 1; i <= size; i++) prefix[i] = prefix[i - 1] + list.get(i - 1);
            for (int i = 1; i <= size; i++) {
                int idx = list.get(i - 1);
                long l = (long) i * idx - prefix[i];
                long r = prefix[size] - prefix[i] - (long) (size - i) * idx;
                ans[idx] = l + r;
            }
        }
        return ans;
    }

    public static long[] distance_n(int[] nums) {
        // 0 1 3 4 7
        // 0 到其他数的距离 1 3 4 7 = 15
        // 1 到其他数的距离, 1 2 3 6, 在 0 到其他数的距离的基础上相加减, 即算出一个增量,
        // 0 变成 1, 增加了 1, 与 0 之前的数的距离增加了 1, 与 1 之后的数的距离减少了 1
        // (1 - 0) * (0) - (1 - 0)(5 - 2) = -3
        // 3 到其他数的距离, 3 2 1 4, (3 - 1)(1) - (3 - 1)(5 - 3) = -1
        // 一般地, 假设第 i 个数到其他数的距离为
        int n = nums.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            List<Integer> list = map.getOrDefault(nums[i], new ArrayList<>());
            list.add(i);
            map.put(nums[i], list);
        }
        long[] ans = new long[n];
        for (List<Integer> list : map.values()) {
            long distance = 0;
            for (int idx : list) distance += idx - list.get(0);
            ans[list.get(0)] = distance;
            for (int i = 1; i < list.size(); i++) {
                int carry = list.get(i) - list.get(i - 1);
                long pre = (long) carry * (i - 1);
                long post = (long) carry * (list.size() - i - 1);
                distance += pre - post;
                ans[list.get(i)] = distance;
            }
        }
        return ans;
    }

}
